package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
public class _234_回文链表 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        if (head.next.next == null) return (head.val == head.next.val);
        // 找到链表的中间节点
        ListNode mid = finMid(head);
        // 反转中间节点后边的所有节点，返回反转链表后的头节点
        ListNode rHead = reverse(mid.next);

        // 记录一下
        ListNode rOldHead = rHead;

        // 左边的头
        ListNode lHead = head;

        // 两边同时往中间走。右边能走到null，就证明链表是回文的
        boolean res = true;
        while (rHead != null) {
            if (rHead.val != lHead.val) {
                res = false;
                break;
            }
            rHead = rHead.next;
            lHead = lHead.next;
        }

        reverse(rOldHead);

        return res;
    }

    /**
     * 反转链表。返回反转后的链表的新的头节点
     *
     * @param head
     */
    private ListNode reverse(ListNode head) {
        if(head == null) return head;
        ListNode newHead = null;
        while (head != null) {
            // 记录下一个节点
            ListNode temp = head.next;
            // 指针反过来指向
            head.next = newHead;
            // 变更新的头节点
            newHead = head;
            // head指针移动
            head = temp;
        }
        return newHead;
    }

    /**
     * 返回链表的中间节点
     * 1>2>3>4>5>6>null   返回 3
     * 1>2>3>4>5>6>7>null 返回 3
     *
     * @param head
     * @return
     */
    private ListNode finMid(ListNode head) {
        // 使用快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 慢指针指向的就是中间节点
        return slow;
    }
}
